package datastructure.sort;

/**
 * 希尔排序是插入排序的变化
 * @author yinlei
 * @date 2018/7/2
 * @since 1.0.0
 */
public class ShellSort implements SortMain.Sort {

    public void sort(int[] arr) {
        int size = arr.length;

        int gap = size / 2;

        while (gap > 0) {
            // 从第gap起，查询数据信息
            for (int i = gap; i < size; i++) {
                int val = arr[i];
                int pos = i;
                // 插入排序，是从后向前寻找位置
                for (int j = i - gap; j > -1; j -= gap) {
                    if (val < arr[j]) {
                        arr[j + gap] = arr[j];
                        pos = j;
                    }
                }
                arr[pos] = val;
            }
            gap = gap / 2;
        }
    }
}
